1. Field of the Invention
The present invention relates to digital image processing methods and more particularly to improved methods for image reduction.
2. Description of the Prior Art
The following are systems representative of the prior art.
U.S. patent application Ser. No. 840,627 filed 3-17-86 of F. C. Mintzer et al, assigned to a common assignee, shows a method for reducing a binary image including the steps of: storing the image in bit sequence; dividing the image into transposable blocks; transposing by look up table, for each block having any nonzero data, each group of 6 bits along a first axis to a group of 5 bits; transposing by look up table, for each block having any nonzero data, each group of 6 bits along a second axis to a group of 5 bits; storing said transposed blocks.
The method of the patent application, while efficient for the intended application, is not able to reduce an image by an arbitrary factor selected by the user as is the present invention. Further, the method of the patent application does not employ a method in which image rotation is used to simplify the reduction algorithm to a single direction which acts on each axis of the image separately; this simplification is unnecessary when the reduction factor is fixed.
U.S. Pat. No. 4,280,143 (Judd) shows apparatus for reduction of image data. Judd divides the input image into units of (possibly) unequal numbers of pels. Judd's method reduces each input unit to a single output pel, taking into account pels from neighboring input subgroups (left of, right of, and above the input unit being compacted) as well as previous output pels. The present invention, in contrast, considers an input window of only three vertically aligned pels. It does not consider neighboring input subgroups or previous output pels. Indeed, no sub-blocks are generated or considered. Furthermore, the present invention computes a multiplicity of outputs at a time, which entails a more efficient software embodiment.
Judd's method handles reductions by fractions (a/b) conceptually by enlarging first by 1:a (through replicating pels) then reducing by b:1, where b would be the size of the input group. This could be clumsy for fractions with large values of a and/or b. The method according to the present invention neither generates nor considers sub-blocks; lines are removed/modified at points calculated by a counter. Thus no additional complexity is introduced if a and/or b are large.
A major feature of the present invention that is not shown by the Judd patent is the double rotation of the image during reduction. This makes it practical to implement in software on a general-purpose computer. The Judd patent describes a hardware implementation. In that environment the reading of columns of bits is straightforward; but it is not clear how that could be done in software.
U.S. Pat. No. 4,303,948 describes both an image reduction process and an image expansion process. The reduction process differs from the method of the present invention in that it does not allow reduction by an arbitrary factor and that it discards bits according to a predetermined pattern without attempting to ensure that no runs are destroyed.
The patented algorithm requires two page memories; it apparently does not allow expansion in situ.
U.S. Pat. No. 4,435,703 deals with a method for displaying predefined dot patterns (which are matrices of binary values); but it does not tell how to create the dot patterns. The method of the present invention shows how to generate the binary dot patterns to be displayed.
U.S. Pat. No. 4,428,065 deals with displaying predefined dot patterns of two different sizes simultaneously on the same display device. It deals with coded information rather than image data. The dot patterns for the two sizes of text are precanned; the patent also does not deal how the dot patterns were generated.
U.S. Pat. No. 3,976,982 is limited to reductions by integer factors. The reduction is done by looking at which color pixel predominates in an MxN field which is to be reduced to a single pixel; adjacent fields are not considered. This patent also shows an enlargement algorithm, but this algorithm is limited to integer factors and consists of merely replicating each pixel enough times to fill a corresponding MxN field.
U.S. Pat. No. 4,267,573 operates by transforming images (e.g. to a log spiral coordinate system).
U.S. Pat. No. 4,153,896 reduces the image first in one dimension and then in the other. This patent relies on special purpose hardware, to read an image in either scan dimension, and does not rotate the image as does the present invention. It is not appropriate for direct implementation in software, since most computers do not have this hardware capability. It is capable of scaling (enlarging or reducing) by an arbitrary factor. However, the reduction process uses essentially a majority-logic system to collapse several pels into one; this would tend to lose fine lines in large reductions.